Corelab Seminar
2010-2011
Panagiotis Cheilaris (Ben Gurion University)
The potential to improve the choice
Abstract.
Given a hypergraph H=(V,E), a vertex coloring C:V->IN is said to be unique-maximum (um for short) if for every hyperedge S in E, the maximum color occurring in S, i.e. max{C(v)|v in S},
occurs in exactly one vertex of S. Um-coloring has several applications, e.g., in frequency assignment in cellular networks.
We study the list version of um-coloring. Given is a hypergraph H=(V,E) and a family L of |V| lists of colors, where each vertex in V is associated with a list. We denote the list associated with v by L(v).
We say that hypergraph H admits a um-coloring from family L if there exists a um-coloring C such that C(v) in L(v). Intuitively, v can only be colored with colors from its list L(v).
The minimum integer x such that "for any family L with |L(v)| >= x for every v in V, H admits a um-coloring from L" is called the um-choice number of H and is denoted by chum(H).
We prove that if a hypergraph H with n vertices is hereditarily k-colorable (in the classic non-monochromatic sense), where k is a constant, then chum(H) = O(logn) and this bound is asymptotically tight.
The proof is constructive and uses a suitable potential function for constructing a um-coloring and analyzing the size of lists needed. As a corollary, we get algorithms for um-coloring hypergraphs
induced by geometric shapes, given lists of logarithmic size.
Joint work with Shakhar Smorodinsky and Marek Sulovský.